import Nat "mo:base/Nat";
import Array "mo:base/Array";
import Debug "mo:base/Debug";


func Paritition(arr:[var Int], low:Nat, high:Nat){
  if(low>=high) return;
   var pivot = arr[low];
   var left=low;
   var right= high;
   while (left < right) {
     while (left < right and arr[right] >= pivot) {
       right -= 1;
     };
     arr[left] := arr[right];
     while (left < right and arr[left] <= pivot) {
       left += 1;
     };
     arr[right] := arr[left];
   };
   arr[right] := pivot;
   if (left >=1)     Paritition(arr,low,left-1);
   Paritition(arr,left+1,high);
 };

func quickSort(arr:[Int]):[Int]{
    var newArr:[var Int] = Array.thaw(arr);
    Paritition(newArr,0,newArr.size()-1);
    Array.freeze(newArr)


  };


func qstest(){
    let arr_test = [10,1500,13,213,1343];
    Debug.print(debug_show(quickSort(arr_test)));
};
qstest();

// let num = [10,1500,13,145,67];
// let numa = quickSort(num);
// var size : Nat = 42 ;
// let x : [var Nat] = Array.init<Nat>(size, 3);
// let a : [var Nat] = [var 1, 2, 3];
// a[2] := 42;
// Debug.print(debug_show(numa));

